#ifndef MYTREE_H
#define MYTREE_H

#include <iostream>

using namespace std;

typedef enum{Link, Thread} NodeTag;

class TreeNode {
private:
    char data;
    TreeNode* leftChild;
    TreeNode* rightChild;
    NodeTag lTag, rTag;

    friend class MyTree;

public:
    TreeNode();
    TreeNode(char data, TreeNode* left = nullptr, TreeNode* right = nullptr, NodeTag lTag = Link, NodeTag rTag = Link);
    ~TreeNode();

    void printNode();
};

class MyTree {
private:
    TreeNode* root;
    bool isThread;
    TreeNode sentinelNode;

    TreeNode* buildTree(const char*&);
    TreeNode* copyTree(TreeNode*);
    void deleteTree(TreeNode*);
    void preOrder(TreeNode* node);
    void inOrder(TreeNode* node);
    void postOrder(TreeNode* node);
    int countLeaf(TreeNode* node);
    int countHeight(TreeNode* node);

public:
    MyTree();
    MyTree(const char[]);
    MyTree(const MyTree&);
    ~MyTree();

    void preOrderTraverse();
    void inOrderTraverse();
    void postOrderTraverse();
    TreeNode& locateNode(const char& v);
    int countLeaf();
    int countHeight();
    bool isThreadedTree();
    bool inOrderThreading();
    TreeNode& preNode(const TreeNode& node);
    TreeNode& nextNode(const TreeNode& node);

    void inOrderThreadingHelper(TreeNode* current, TreeNode*& prev);
};

struct HuffmanNode {
    int freq;               
    int code[100];          
    HuffmanNode* left, *right; 

    HuffmanNode(int f);
};

class HuffmanTree {
public:

    HuffmanTree(const int& size, const int* freq);
    ~HuffmanTree();

    void printHuffmanCodes();

private:
    int size; 
    HuffmanNode** nodes; 
    HuffmanNode* createNode(int freq) const; 

    void printCodes(HuffmanNode* root, int* arr, int top, HuffmanNode* nodeList[], int& index) const;
    void sortNodes(HuffmanNode* nodes[], int size) const;
    void destroyTree(HuffmanNode* root);
};

#endif 
